import javax.swing.plaf.basic.BasicSplitPaneUI;
import java.util.jar.JarEntry;

public class Sort {
    public  void insertSort(int[] array){
//       插入排序就是从第二个数据开始依次和前一个数值比较,这样进行移动,每一次完整的一定都会使前面的数据变得有序,直到遍历完整个数组

        for(int i=1;i<array.length;i++){
//            从第二个元素开始比较,i的大小是不断增加的
            int temp=array[i];
            int j=i-1;
            for(;j>=0;j--){
//                与temp的值比较即可,这里是升序排列
                if(temp>array[j]){
//                    这里是不需要做移动的,并且由于前面的数字已经是有序的,所以直接退出循环即可,
                    break;
                }else{
//                    当比这个数字大时就需要交换位置然后,然后继续向前移动,比较剩余数字即可
                    array[j+1]=array[j];
                }
//             当退出循环循环之后,需要设置array[i+1]的值位temp,这是因为如果进入了else,然后退出循环之后,
//             总有两个位置的数字相同,这是需要设置
//              序号较小的元素位temp
            }
            array[j+1]=temp;
        }
    }
//希尔排序,可以说是对插入排序的改进.就是把数据分组,多进行几次排序.
    public void shellSort(int[] array){
//        这里确定分组情况,对每个分组都进行快速排序,直到最后看成一组进行排序.这里按照每次/2.进行分组
        int gap=array.length;
        while(gap>1){
            gap/=2;
//            这里进行的还是一个插入排序
            shell(array,gap);
        }
    }
    public void shell(int[] array,int gap){
//        i的取值应该是gap的值,还是,并且每次+1即可,这样可以保证依次遍历,把所有分组都遍历完
        for(int i=gap;i<array.length;i++){
            int temp=array[i];
//            这里使用j
            int j=i-gap;
            for(;j>0;j-=gap){
                if(temp>array[j]){
                    break;
                }else{
                    array[j+gap]=array[j];
                }
            }
            array[j+gap]=temp;
        }
    }
//    接下来时选择排序,这里进行升序排序 这个的思路就是选中第一个元素,从第二个元素开始,向后遍历,找到小于第一个元素并且是最小的,和第一个元素
//    交换位置.这样依次遍历,会使数组有序
    public void selectSort1(int[] array){
        for(int i=0;i<array.length;i++){
            int minIndex=i;
            int j=i+1;
            for(;j<array.length;j++){
                if(array[j]<array[minIndex]){
                       minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    public static void swap(int[] array, int i, int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
//    第二种选择排序的方法是一次遍历直接得出,最大值和最小值.
    public void selectSort2(int[] array){
//       还是一样的
       int left=0;
       int right=array.length;
       while(left<right){
//           在一次遍历中找出最大值和最小值
           int minIndex=left;
           int maxIndex=left;
//           遍历数组,找出最大值和最小值
           for(int i=left+1;i<array.length;i++){
               if(array[i]<array[minIndex]){
                   minIndex=i;
               }
               if(array[i]>array[maxIndex]){
                   maxIndex=i;
               }
           }
           if(maxIndex==left){
             maxIndex=minIndex;
           }
           swap(array,minIndex,left);
           swap(array,maxIndex,right);
           left++;
           right--;
       }
    }
//    接着写快速排序.
//    快速排序第一种写法,首先是以第一个元素为基准,比这个元素大的放在这个元素右边,比这个元素小的,放在这个元素左边.以此类推`
    public static void quickSort(int[] array){
//        传入数组.left位置,right位置即可
        quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int start,int end){
//        什么时候结束呢?
//        当start小于end时,都不会停止,所以先判断这两个的值
        if(start>=end){
            return;
        }
//        首先得到pivot,然后对左边和右边都进行快速排序
//        partition
        int pivot=partition2(array,start,end);
//        对左边和右边都进行快排
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    public static int partition1(int[] array,int left,int right){
//        以第一个元素为基准
        int temp=array[left];
        int i=left;
        while(left<right){
//            从右边开始,找小于基准元素的
            while(left<right&&array[right]>=temp){
                right--;
            }
//            那从左边开始就是找的大于基准元素的
            while(left<right&&array[left]<=temp){
                left++;
            }
//            出了循环就是找到了,交换即可,然后继续找,直到left和right相等.
            swap(array,left,right);
        }
//        出了这个循环说明left==right,此时返回即可.这样一趟排序,是会把left这个位置的元素归位的,需要把left位置的元素设置为temp
//        让这个元素归位,由于是right先移动的,所以共同指向的这个元素一定是小于temp的,能够满足,左边的元素都比temp小,右边的元素都比
//        temp大,这样一来,就把temp这个元素归位了.记录原始位置交换即可.
        swap(array,i,left);
        return left;
    }
//    上面的是第一种写法,还有第二种写法,挖坑法,
    public static int partition2(int[] array,int left,int right){
//       挖第一个坑
        int temp=array[left];
//        left小于right时,不断填坑挖坑
        while(left<right){
//            还是从右边开始,找小于这个基准的进行填坑
            while(left<right&&array[right]>=temp){
                right--;
            }
//            两种情况,进行判断
            if(left>=right){
                break;
            }
//            填坑
            array[left]=array[right];
//            现在的坑成为了right这个下标
            while(left<right&&array[left]<=temp){
                left++;
            }
//            两种情况,进行判断
            if(left>=right){
                break;
            }
            array[right]=array[left];
        }
        array[left]=temp;
        return left;
    }
































}
